#pragma once
#pragma once
#include <vector>

class UnionSet
{
public:
	UnionSet(size_t size) :_set(size, -1) {}

	size_t FindRoot(int index)
	{
		while (_set[index] >= 0)
		{
			index = _set[index];
		}
		return index;
	}

	void Union(int index1, int index2)
	{
		int root1 = FindRoot(index1);
		int root2 = FindRoot(index2);
		if (root1 != root2)
		{
			_set[root1] += _set[root2];
			_set[root2] = root1;
		}
	}

	size_t TreeNum()
	{
		int answer = 0;
		for (auto& e : _set)
		{
			if (e < 0)
			{
				answer++;
			}
		}
		return answer;
	}

	std::vector<int> _set;
};
